package class03_一些基础的数据结构.test;

import java.util.LinkedList;
import java.util.Stack;

public class Code03_DoubleEndsQueueToStackAndQueue {
    public static class Node<T>{
        public T value;
        public Node<T> last;
        public Node<T> next;

        public Node(T head) {
            value = head;
        }
    }
    //双端队列
    public static class DoubleEndsQueue<T>{
        public Node<T> head;
        public Node<T> tail;

        public void andFromHead(T value){
            Node<T> cur = new Node<>(value);
            if(head == null){
                head = cur;
                tail = cur;
            }else {
                cur.next = head;
                head.last = cur;
                head = cur;
            }
        }
        public void andFromBottom(T value){
            Node<T> cur = new Node<>(value);
            if(tail == null){
                head = cur;
                tail = cur;
            }else {
                cur.last = tail;
                tail.next = cur;
                tail = cur;
            }
        }
        public T popFromHead(){
            if(head == null){
                return null;
            }
            Node<T> cur = head;
            if(head == tail){
                head = null;
                tail = null;
            }else {
                head = cur.next;
                head.last = null;
                cur.next = null;
            }
            return cur.value;
        }
        public T popFromBottom(){
            if(tail == null){
                return null;
            }
            Node<T> cur = tail;
            if(head == tail){
                head = null;
                tail = null;
            }else {
                tail = cur.last;
                tail.next = null;
                cur.last = null;
            }
            return  cur.value;
        }
        public boolean isEmpty(){
           return head == null ? true : false;
        }
    }
    public static class myStack<T>{
        private DoubleEndsQueue<T> stack;
        public myStack(){
            stack = new DoubleEndsQueue<>();
        }
        public void push(T val){
            stack.andFromHead(val);
        }
        public T pop(){
            return stack.popFromHead();
        }
        public boolean isEmpty(){
            return stack.isEmpty();
        }
    }
    public static class myQueue<T>{
        private DoubleEndsQueue<T> queue;
        public myQueue(){
            queue = new DoubleEndsQueue<>();
        }
        public void push(T val){
            queue.andFromBottom(val);
        }
        public T poll(){
            return queue.popFromHead();
        }
        public boolean isEmpty(){
            return queue.isEmpty();
        }
    }

    public static void main(String[] args) {
//        myStack<Object> objectmyQueue = new myStack<>();
//        objectmyQueue.push(3);
//        objectmyQueue.push(5);
//        objectmyQueue.push(1);
//        objectmyQueue.push(2);
//        objectmyQueue.push(4);
//        while (!objectmyQueue.isEmpty()){
//            System.out.println(objectmyQueue.pop());
//        }
        int oneTestDataNum = 500;
        int testTimes = 1000000;
        int value = 10000;
        for (int i = 0; i < testTimes; i++) {
            Stack<Integer> stack = new Stack<>();
            LinkedList<Integer> queue = new LinkedList<>();
            myStack<Integer> myStack = new myStack<>();
            myQueue<Integer> myQueue = new myQueue<>();
            for (int j = 0; j < oneTestDataNum; j++) {
                int nums = (int)(Math.random()*value);
                if(stack.isEmpty()){
                    stack.push(nums);
                    myStack.push(nums);
                }else {
                    if(Math.random() < 0.5){
                        stack.push(nums);
                        myStack.push(nums);
                    }else {
                        if(!isEqual(stack.pop(),myStack.pop())){
                            System.out.println("stack Oops!!!");
                        }
                    }
                }
                int nums2 = (int)(Math.random() * value);
                if(queue.isEmpty()){
                    queue.push(nums2);
                    myQueue.push(nums2);
                }else {
                    if(Math.random() < 0.5){
                        queue.push(nums2);
                        myQueue.push(nums2);
                    }else {
                        if(!isEqual(queue.poll(),myQueue.poll())){
                            for (Integer val : queue) {
                                System.out.print(val + " ");
                            }
                            System.out.println();
                            while (!myQueue.isEmpty()){
                                System.out.print(myQueue.poll() +" ");
                            }
                            System.out.println("queue Oops!!!");
                        }
                    }
                }
            }
        }
        System.out.println("Finish!");
    }

    public static boolean isEqual(Integer o1, Integer o2) {
        if (o1 == null && o2 != null) {
            return false;
        }
        if (o1 != null && o2 == null) {
            return false;
        }
        if (o1 == null && o2 == null) {
            return true;
        }
        return o1.equals(o2);
    }
}
